//
// Created by Administrator on 2021/11/7.
//
#include <math.h>
#include <string.h>
#include "stdio.h"
#include "WGraph.h"
int judge(char a[], char b[]){
    /*
     * 如果两个单词相同，或者差距字符超过1个，返回0
     * a字典序小于b字典序，返回-1
     * a字典序大于b字典序，返回1
     * */
    if (abs(strlen(a) - strlen(b)) > 1)
        return 0;
    if (strlen(a) == strlen(b)) {
        int length = strlen(a);
        int differences = 0;
        int gap = 0;
        for (int i = 0; i < length; ++i) {
            if (a[i] != b[i]) {
                differences++;
                gap = (int)a[i] - (int)b[i];
            }
        }
        if (differences == 0 || differences > 1) {
            return 0;
        } else {
            return gap < 0 ? -1 : 1;
        }
    } else {
        int length = strlen(a) < strlen(b) ? strlen(a) : strlen(b);
        int flag = 0;
        int preResult;
        for (int i = 0; i < length; ++i) {
            if (flag == 0) {
                if (a[i] != b[i]) {
                    preResult = a[i] < b[i] ? -1 : 1;
                    flag = 1;
                    i--;
                    continue;
                }
            }
            if (flag == 1) {
                if (a[i + (strlen(a) > strlen(b) ? 1 : 0)] != b[i + (strlen(a) > strlen(b) ? 0 : 1)]) {
//                    printf("0\n");
//                    printf("i == %d\n", i);
//                    printf("%d, %d\n", strlen(a), strlen(b));
//                    printf("%c %c\n", a[i + (strlen(a) > strlen(b) ? 1 : 0)], b[i + (strlen(a) > strlen(b) ? 0 : 1)]);
                    return 0;
                }
            }
        }
        if (flag == 1) {
            return preResult;
        } else {
            return strlen(a) < strlen(b) ? -1 : 1;
        }
    }
    return 0;
}
int valueIsInArray(int a[], int currentNum,  int value) {
    for (int i = 0; i <= currentNum; ++i) {
        if (a[i] == value)
            return 1;
    }
    return 0;
}
void getMaxSequence(Graph graph, int numbers, int loadedItem[], int currentIndex, int* length, int* maxLength, int loaded[][numbers], int* sum) {
    int tempLength = *length;
    for (int i = 0; i < numbers; ++i) {
        if (valueIsInArray(loadedItem, currentIndex, i) == 1)
            continue;
        if (adjacent(graph, loadedItem[currentIndex], i) == 1) {
            loadedItem[++currentIndex] = i;
            *length = tempLength + 1;
            if (*maxLength < *length) {
                *sum = 1;
                *maxLength = *length;
                for (int j = 0; j < *maxLength; ++j) {
                    loaded[*sum - 1][j] = loadedItem[j];
                }
            } else if (*maxLength == *length) {
                *sum += 1;
                for (int j = 0; j < *maxLength; ++j) {
                    loaded[(*sum)-1][j] = loadedItem[j];
                }
            }
            getMaxSequence(graph, numbers, loadedItem, currentIndex, length, maxLength, loaded, sum);
            currentIndex--;
        }
    }
}
int main() {
    int numbers = 0;
//    printf("Enter a number:");
//    scanf("%d", &numbers);
//    numbers = 6;
//    char words[6][31] = {{"lad"}, {"lag"}, {"lap"}, {"tap"}, {"tip"}, {"top"}};
//    numbers = 8;
//    char words[8][31] = {{"bad"}, {"ban"}, {"dad"}, {"dan"}, {"lad"}, {"lap"}, {"mad"}, {"tap"}};
    numbers = 6;
    char words[6][31] = {{"east"}, {"eat"}, {"eats"}, {"fast"}, {"fist"}, {"foist"}};
//    numbers = 5;
//    char words[5][31] = {{"east"}, {"eat"}, {"eats"}, {"fast"}, {"fist"}};
//    for (int i = 0; i < numbers; ++i) {
//        printf("Enter a word:");
//        scanf("%s", words[i]);
//    }
    Graph graph = newGraph(numbers);
    for (int i = 0; i < numbers; ++i) {
        for (int j = 0; j < numbers; ++j) {
            if (judge(words[i], words[j]) == -1) {
                Edge edge;
                edge.v = i;
                edge.w = j;
                edge.weight = 1;
                insertEdge(graph, edge);
            } else if (judge(words[i], words[j]) == 1) {
                struct Edge edge;
                edge.v = j;
                edge.w = i;
                edge.weight = 1;
                insertEdge(graph, edge);
            }
        }
    }
//    showGraph(graph);
    for (int i = 0; i < numbers; ++i) {
        printf("%s: ", words[i]);
        for (int j = 0; j < numbers; ++j) {
            if (i == j)
                continue;
            if (adjacent(graph, i, j) == 1) {
                printf(" %s", words[j]);
            }
        }
        printf("\n");
    }
    printf("\n");


    int maxLength = -1;
    int loaded[100][numbers];
    int allSum = 0;
    for (int i = 0; i < numbers; ++i) {
        int tempMaxLength = 1;
        int tempLoaded[100][numbers];
        int sum = 1;
        int currentIndex = 0;
        int loadedItem[numbers];
        loadedItem[0] = i;
        int length = 1;
        getMaxSequence(graph, numbers, loadedItem, currentIndex, &length, &tempMaxLength, tempLoaded, &sum);
        if (maxLength < tempMaxLength) {
            allSum = sum;
            maxLength = tempMaxLength;
            for (int k = 0; k < sum; ++k) {
                for (int j = 0; j < maxLength; ++j) {
                    loaded[k][j] = tempLoaded[k][j];
                }
            }
        } else if (maxLength == tempMaxLength) {
            for (int j = 0; j < sum; ++j) {
                for (int k = 0; k < maxLength; ++k) {
                    loaded[j + allSum][k] = tempLoaded[j][k];
                }
            }
            allSum += sum;
        }
    }
    printf("Maximum sequence length: %d\n", maxLength);
    printf("Maximal sequence(s):\n");
    for (int j = 0; j < allSum; ++j) {
        for (int i = 0; i < maxLength; ++i) {
            if (i != 0)
                printf(" -> ");
            printf("%s",words[loaded[j][i]]);
        }
        printf("\n");
    }
}

